//package com.qying.myguava.util;
//
//import sun.reflect.generics.tree.Tree;
//
//import javax.swing.text.Segment;
//import java.io.ObjectStreamField;
//import java.io.Serializable;
//import java.lang.reflect.ParameterizedType;
//import java.lang.reflect.Type;
//import java.util.*;
//import java.util.concurrent.ConcurrentHashMap;
//import java.util.concurrent.ConcurrentMap;
//import java.util.concurrent.locks.LockSupport;
//import java.util.function.BiConsumer;
//import java.util.function.BiFunction;
//import java.util.function.Function;
//
///**
// * @Author 秦扬
// * @Date 2021/9/16 16:36
// */
//public class MyConcurrentHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable {
//
//
//    private static final int MAXIMUM_CAPACIYT = 1 << 30;
//
//    private static final int DEFAULT_CAPACITY = 16;
//
//    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//
//    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//
//    private static final float LOAD_FACTOR = 0.75f;
//
//    static final int TREEIFY_THRESHOLD = 8;
//
//    static final int UNTREEIFY_THRESHOLD = 6;
//
//    static final int MIN_TREEIFY_CAPACITY = 64;
//
//    private static final int MIN_TRANSFER_STRIDE = 16;
//
//    private static int RESIZE_STAMP_BITS = 16;
//
//    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS));
//
//    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
//
//    static final int MOVED = -1;
//    static final int TREEBIN = -2;
//    static final int RESERVED = -3;
//    static final int HASH_BITS = 0x7fffffff;
//
//    static final int NCPU = Runtime.getRuntime().availableProcessors();
//
//    private static final ObjectStreamField[] serialPersistentFields = {
//            new ObjectStreamField("segments", Segment[].class),
//            new ObjectStreamField("segmentMask", Integer.TYPE),
//            new ObjectStreamField("segmentShift", Integer.TYPE)
//    };
//
//    static class Node<K, V> implements Map.Entry<K, V> {
//        final int hash;
//        final K key;
//        final V val;
//        volatile Node<K, V> next;
//
//        Node(int hash, K key, V val, Node<K, V> next) {
//            this.hash = hash;
//            this.key = key;
//            this.val = val;
//            this.next = next;
//        }
//
//        public final K getKey() {
//            return key;
//        }
//
//        public final V getValue() {
//            return val;
//        }
//
//        public final int hashCode() {
//            return key.hashCode() ^ val.hashCode();
//        }
//
//        @Override
//        public String toString() {
//            return key + "=" + val;
//        }
//
//        public final V setValue(V value) {
//            throw new UnsupportedOperationException();
//        }
//
//        public final boolean equals(Object o) {
//            Object k, v, u;
//            Map.Entry<?, ?> e;
//            return ((o instanceof Map.Entry) &&
//                    (k = (e = (Map.Entry<?, ?>) o).getKey()) != null &&
//                    (v = e.getValue()) != null &&
//                    (k == key || k.equals(key)) &&
//                    (v == (u = val) || v.equals(u)));
//        }
//
//        Node<K, V> find(int h, Object k) {
//            Node<K, V> e = this;
//            if (k != null) {
//                do {
//                    K ek;
//                    if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek))))
//                        return e;
//                } while ((e = e.next) != null);
//            }
//            return null;
//        }
//
//    }
//
//    static final int spread(int h) {
//        return (h ^ (h >>> 16)) & HASH_BITS;
//    }
//
//    private static final int tableSizeFor(int c) {
//        int n = c - 1;
//        n |= n >>> 1;
//        n |= n >>> 2;
//        n |= n >>> 4;
//        n |= n >>> 8;
//        n |= n >>> 16;
//        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACIYT) ? MAXIMUM_CAPACIYT : n + 1;
//    }
//
//    static Class<?> compareableClassFor(Object x) {
//        if (x instanceof Comparable) {
//            Class<?> c;
//            Type[] ts, as;
//            Type t;
//            ParameterizedType p;
//            if ((c = x.getClass()) == String.class)
//                return c;
//
//            if ((ts = c.getGenericInterfaces()) != null) {
//                for (int i = 0; i < ts.length; ++i) {
//                    if (((t = ts[i]) instanceof ParameterizedType)
//                            && ((p = (ParameterizedType) t).getRawType() == Comparable.class)
//                            && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c)
//                        return c;
//                }
//            }
//        }
//        return null;
//    }
//
//    static int compareCompareables(Class<?> kc, Object k, Object x) {
//        return (x == null || x.getClass() != kc ? 0 : ((Comparable) k).compareTo(x));
//    }
//
//    transient volatile Node<K, V>[] table;
//
//    private transient volatile Node<K, V>[] nextTable;
//
//    private transient volatile long baseCount;
//
//    private transient volatile int sizeCtl;
//
//    private transient volatile int transferIndex;
//
//    private transient volatile int cellsBusy;
//
//    private transient volatile CounterCell[] counterCells;
//
//
//    public static class KeySetView<K, V> extends CollectionView<K, V> implements Set<K>, java.io.Serializable {
//
//        private static final long serialVersionUID = 724901236763182397L;
//
//        private final V value;
//
//        KeySetView(MyConcurrentMap<K, V> map, V value) {
//            super(map);
//            this.value = value;
//        }
//
//        public V getMappedValue() {
//            return value;
//        }
//
//        public boolean contains(Object o) {
//            return map.containsKey(o);
//        }
//
//        public boolean remove(Object o) {
//            return map.remove(o) != null;
//        }
//
//        public Iterator<K> iterator() {
//            Node<K, V>[] t;
//            MyConcurrentMap<K, V> m = map;
//            int f = (t = m.table) == null ? 0 : t.length;
//            return new Ke
//        }
//
//    }
//
////    static final class KeyIterator<K,V> extends Base
//
////    static class BaseIterator<K,V> extends Tr
//
//
//    static class Traverser<K,V> {
//        Node<K,V>[] tab;
//        Node<K,V> next;
//        TableStack<K,V> stack,spare;
//        int index;
//        int baseIndex;
//        int baseLimit;
//        final int baseSize;
//
//        public Traverser(Node<K, V>[] tab, int size, int index, int limit) {
//            this.tab = tab;
//            this.baseSize = size;
//            this.baseIndex = this.index = index;
//            this.baseLimit = limit;
//            this.next =null;
//        }
//
//        final Node<K,V> advance(){
//            Node<K,V> e;
//            if ((e = next) != null){
//                e= e.next;
//            }
//
//            for (;;) {
//                Node<K,V>[] t; int i,n;
//                if (e!=null){
//                    return next = e;
//                }
//
//                if (baseIndex >= baseLimit || (t = tab) == null || (n = t.length) <= (i =index) || i<0) {
//                    return next = null;
//                }
//
//                if ((e = tabAt(t,i)) != null && e.hash < 0) {
//                    if (e instanceof ForwardingNode) {
//                        tab = ((ForwardingNode<K,V>) e).nextTable;
//                        e= null;
//                        pushState(t,i,n);
//                        continue;
//                    }else if (e instanceof TreeBin) {
//
//                    }
//
//                }
//            }
//        }
//
//        private void pushState(Node<K,V>[] t, int i , int n) {
//            TableStack<K,V> s = spare;
//            if (s!= null) {
//                spare = s.next;
//            }else {
//                s = new TableStack<K,V>();
//            }
//            s.tab = t;
//            s.length = n;
//            s.index = i;
//            s.next = stack;
//            stack =s;
//        }
//
//    }
//
//    static final class TreeBin<K,V> extends Node<K,V> {
//
//        TreeNode<K,V> root;
//        volatile  TreeNode<K,V> first;
//        volatile Thread waiter;
//        volatile int  lockState;
//
//        static final int WRITER =1;
//        static final int WAITER =2;
//        static final int READER =4;
//
//        static int tieBreakOrder(Object a, Object b) {
//            int d;
//            if (a== null || b == null || (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0) {
//                d =(System.identityHashCode(a) <= System.identityHashCode(b) ? -1:1);
//            }
//            return d;
//        }
//
//        TreeBin(TreeNode<K,V> b) {
//            super(TREEBIN,null,null, null);
//            this.first = b;
//
//            TreeNode<K,V> r = null;
//            for (TreeNode<K,V> x =b, next; x != null; x= next) {
//                next = (TreeNode<K, V>) x.next;
//                x.left = x.right = null;
//                if (r == null ) {
//                    x.parent = null;
//                    x.red = false;
//                    r= x;
//                }else {
//                    K k = x.key;
//                    int h = x.hash;
//                    Class<?> kc = null;
//                    for (TreeNode<K,V> p = r;;) {
//                        int dir , ph;
//                        K pk = p.key;
//                        if ((ph = p.hash) > h) {
//                            dir = -1;
//                        }else if (ph < h) {
//                            dir = 1;
//                        }else if ((kc == null && (kc = compareableClassFor(k)) == null)
//                                || (dir = compareCompareables(kc, k, pk)) == 0) {
//                            dir = tieBreakOrder(k,pk);
//                        }
//                        TreeNode<K,V> xp = p;
//
//                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
//                            x.parent = xp;
//                            if (dir <= 0) {
//                                xp.left = x;
//                            }else {
//                                xp.right = x;
//                            }
//                            r = balanceInsertion(r,x);
//                            break;
//                        }
//                    }
//                }
//            }
//        }
//
//        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x){
//            x.red = true;
//            for (TreeNode<K,V> xp, xpp,xppl,xppr;;) {
//                if ((xp = x.parent) == null) {
//                    x.red = false;
//                    return x;
//                }else if (!xp.red || (xpp = xp.parent) == null) {
//                    return root;
//                }
//
//                if (xp == (xppl = xpp.left)) {
//                    if ((xppr = xpp.right) != null && xppr.red) {
//                        xppr.red = false;
//                        xp.red = false;
//                        xpp.red = true;
//                        x= xpp;
//                    }else {
//                        if (x== xp.right) {
//                            root  = rotateRight(root,x= xp);
//                            xpp = (xp = x.parent) == null ? null : xp.parent;
//                        }
//
//                        if (xp != null) {
//                            xp.red = false;
//                            if (xpp != null ){
//                                xpp.red = true;
//                                root = rotateLeft(root,xpp);
//                            }
//                        }
//                    }
//
//                }
//            }
//        }
//
//        private static final sun.misc.Unsafe U;
//        private static final long LOCKSTATE;
//        static {
//            try {
//                U = sun.misc.Unsafe.getUnsafe();
//                Class<?> k = TreeBin.class;
//                LOCKSTATE = U.objectFieldOffset(k.getDeclaredField("lockState"));
//            }catch (Exception e) {}
//        }
//
//        private final void lockRoot(){
//            if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
//                contendedLock();
//        }
//
//        private final void contendedLock(){
//            boolean waiting = false;
//            for (int s ;;) {
//                if (((s = lockState) & ~WAITER) == 0 ) {
//                    if (U.compareAndSwapInt(this,LOCKSTATE,s,WRITER)){
//                        if (waiting)
//                            waiter = null;
//                        return;
//                    }
//                }else if ((s & WAITER) == 0) {
//                    if (U.compareAndSwapInt(this,LOCKSTATE,s, s|WAITER)){
//                        waiting =true;
//                        waiter = Thread.currentThread();
//                    }
//                }else if (waiting) {
//                    LockSupport.park(this);
//                }
//            }
//        }
//
//        final Node<K,V> find(int h, Object k) {
//            if (k != null) {
//                for (Node<K,V> e= first; e!= null; ) {
//                    int s; K ek;
//
//                    if (((s = lockState) & (WAITER | WRITER)) != 0) {
//                        if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) {
//                            return e;
//                        }
//                        e = e.next;
//                    }else if (U.compareAndSwapInt(this,LOCKSTATE,s,s+READER)) {
//                        TreeNode<K,V> r,p;
//                        try {
//                            p = ((r = root) == null ? null : r.findTreeNode(h,k,null));
//                        }finally {
//                            Thread w;
//                            if (U.getAndAddInt(this,LOCKSTATE,-READER) == (READER | WAITER)
//                                    && (w=waiter) != null) {
//                                LockSupport.unpark(w);
//                            }
//                        }
//                        return p;
//                    }
//                }
//            }
//            return null;
//        }
//
//        final TreeNode<K,V> putTreeVal(int h, K k , V v) {
//            Class<?> kc = null;
//            boolean searched =false;
//            for (TreeNode<K,V> p = root;;) {
//                int dir , ph; K pk;
//                if (p == null) {
//                    first = root = new TreeNode<K,V>(h,k,v,null,null);
//                    break;
//                }else if ((ph = p.hash) > h) {
//                    dir = -1;
//                }else if (ph < h) {
//                    dir = 1;
//                }else if ((pk = p.key) == k || (pk != null&& k.equals(pk)) ){
//                    return p;
//                }else if ((kc == null && (kc = compareableClassFor(k))== null)
//                        || (dir = compareCompareables(kc,k,pk)) == 0) {
//                    if (!searched) {
//                        TreeNode<K,V> q,ch;
//                        searched = true;
//                        if (((ch = p.left) != null && (q =ch.findTreeNode(h,k,kc))!= null
//                        || ((ch = p.right) != null && (q = ch.findTreeNode(h,k,kc))!=null))){
//                            return q;
//                        }
//                    }
//                    dir = tieBreakOrder(k,pk);
//                }
//
//                TreeNode<K,V> xp = p;
//
//                if ((p = (dir <=0) ? p.left : p.right) == null) {
//                    TreeNode<K,V> x,f = first;
//                    first = x = new TreeNode<>(h,k,v,f,xp);
//
//                    if (f != null) {
//                        f.prev = x;
//                    }
//                    if (dir <= 0 ) {
//                        xp.left =x;
//                    }else {
//                        xp.right = x;
//                    }
//
//                    if (!xp.red) {
//                        x.red = true;
//                    }else {
//                        lockRoot();
//
//                        try {
//                            root = balanceInsertion(root,x);
//                        }finally {
//                            unlockRoot();
//                        }
//                    }
//                    break;
//                }
//            }
//
//            assert checkInvariants(root);
//            return null;
//        }
//
//        final boolean removeTreeNode(TreeNode<K,V> p){
//            TreeNode<K, V> next = (TreeNode<K, V>) p.next;
//            TreeNode<K, V> prev = p.prev;
//            TreeNode<K, V> r,rl;
//
//            if (prev == null) {
//
//            }
//
//
//        }
//
//
//        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
//            TreeNode<K,V> l,pp,lr;
//            if (p != null && (l = p.left) != null) {
//                if ((lr = p.left = l.right) != null) {
//                    lr.parent = p;
//                }
//                if ((pp = l.parent = p.parent) == null) {
//                    (root = l).red = false;
//                }else if (pp.right == p) {
//                    pp.right = l;
//                }else {
//                    pp.left =l;
//                }
//                l.right = p;
//            }
//            return root;
//        }
//
//
//        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
//                                              TreeNode<K,V> p) {
//            TreeNode<K,V> r,pp,rl;
//            if (p != null && (r = p.right) != null) {
//                if ((rl = p.right = r.left) != null) {
//                    rl.parent = p;
//                }
//                if ((pp = r.parent = p.parent) == null) {
//                    (root = r).red = false;
//                }else if (pp.left == p) {
//                    pp.left = r;
//                }else {
//                    pp.right = r;
//                }
//
//                r.left = p;
//                p.parent = r;
//            }
//            return root;
//        }
//
//
//
//
//    }
//
//    static final class TreeNode<K,V> extends Node<K,V>{
//        TreeNode<K,V> parent;
//        TreeNode<K,V> left;
//        TreeNode<K,V> right;
//        TreeNode<K,V> prev;
//        boolean red;
//
//        TreeNode(int hash, K key, V val, Node<K,V> next, TreeNode<K,V> parent) {
//            super(hash,key,val,next);
//            this.parent = parent;
//        }
//
//        Node<K,V> find(int h, Object k) {
//            return findTreeNode(h,k,null);
//        }
//
//        TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
//            if (k != null) {
//                TreeNode<K,V> p = this;
//                do {
//                    int ph,dir; K pk; TreeNode<K,V> q;
//                    TreeNode<K,V> pl = p.left , pr = p.right;
//                    if ((ph = p.hash) > h) {
//                        p = pl;
//                    }else if (ph < h) {
//                        p = pr;
//                    }else if ((pk = p.key) == k || (pk != null && k.equals(pk))) {
//                        return p;
//                    }else if (pl == null) {
//                        p = pr;
//                    }else if (pr == null) {
//                        p = pl;
//                    }else if ((kc !=null || (kc = compareableClassFor(k))!= null) &&
//                            (dir = compareCompareables(kc,k,pk)) != 0) {
//                        p = (dir < 0) ? pl : pr;
//                    }else if ((q = pr.findTreeNode(h, k, kc)) != null){
//                        return q;
//                    }else {
//                        p = pl;
//                    }
//                }while (p != null);
//            }
//            return null;
//        }
//
//
//    }
//
//    static final class ForwardingNode<K,V> extends Node<K,V> {
//        final Node<K,V>[] nextTable;
//
//        ForwardingNode(Node<K,V>[] tab) {
//            super(MOVED, null, null, null);
//            this.nextTable = tab;
//        }
//
//        Node<K,V> find(int h, Object k) {
//            outer: for(Node<K,V>[] tab = nextTable;;) {
//                Node<K,V> e; int n;
//                if (k == null || tab == null || (n = tab.length) == 0
//                || (e= tabAt(tab, (n-1) & h))==null) {
//                    return null;
//                }
//
//                for (;;) {
//                    int eh; K ek;
//                    if ((eh = e.hash) == h && ((ek = e.key) == k || (ek != null && k.equals(ek))))
//                        return e;
//
//                    if (eh < 0) {
//                        if (e instanceof ForwardingNode) {
//                            tab = ((ForwardingNode<K,V>)e).nextTable;
//                            continue outer;
//                        }else {
//                            return e.find(h,k);
//                        }
//                    }
//
//                    if ((e = e.next) == null) {
//                        return null;
//                    }
//                }
//            }
//        }
//
//    }
//
//    static final class TableStack<K,V> {
//        int length;
//        int index;
//        Node<K,V>[] tab;
//        TableStack<K,V> next;
//    }
//
//    abstract static class CollectionView<K, V, E> implements Collection<E>, java.io.Serializable {
//        private static final long serialVersionUID = 72490692123182397L;
//
//        final MyConcurrentMap<K, V> map;
//
//        CollectionView(MyConcurrentMap<K, V> map) {
//            this.map = map;
//        }
//
//        public MyConcurrentMap<K, V> getMap() {
//            return map;
//        }
//
//        public final void clear() {
//            map.clear();
//        }
//
//        public final int size() {
//            return map.size();
//        }
//
//        public final boolean isEmpty() {
//            return map.isEmpty();
//        }
//
//        public abstract Iterator<E> iterator();
//
//        public abstract boolean contains(Object o);
//
//        public abstract boolean remove(Object o);
//
//        private static final String oomeMsg = "Required array size too large";
//
////        public final Object[] toArray(){
////            map.ma
////        }
//    }
//
//    private static final sun.misc.Unsafe U;
//
//    private static final long SIZECTL;
//
//    private static final long TRANSFERINDEX;
//
//    private static final long BASECOUNT;
//
//    private static final long CELLSBUSY;
//
//    private static final long CELLVALUE;
//
//    private static final long ABASE;
//    private static final int ASHIFT;
//
//    static final class CounterCell {
//        volatile long value;
//
//        CounterCell(long x) {
//            value = x;
//        }
//    }
//
//    static {
//        try {
//            U = sun.misc.Unsafe.getUnsafe();
//
//            Class<?> k = ConcurrentMap.class;
//
//            SIZECTL = U.objectFieldOffset(k.getDeclaredField("sizeCtl"));
//            TRANSFERINDEX = U.objectFieldOffset(k.getDeclaredField("transferIndex"));
//            BASECOUNT = U.objectFieldOffset(k.getDeclaredField("baseCount"));
//            CELLSBUSY = U.objectFieldOffset
//                    (k.getDeclaredField("cellsBusy"));
//
//            Class<?> ck = CounterCell.class;
//
//            CELLVALUE = U.objectFieldOffset(ck.getDeclaredField("value"));
//            Class<?> ak = Node[].class;
//            ABASE = U.arrayBaseOffset(ak);
//            int scale = U.arrayBaseOffset(ak);
//
//            if ((scale & (scale - 1)) != 0) {
//                throw new Error();
//            }
//            ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
//
//        } catch (Exception e) {
//        }
//    }
//
//    static final <K, V> Node<K, V> tabAt(Node<K, V>[] tab, int i) {
//        return (Node<K, V>) U.
//    }
//
//    @Override
//    public Set<Entry<K, V>> entrySet() {
//        return null;
//    }
//
//    @Override
//    public V getOrDefault(Object key, V defaultValue) {
//        return null;
//    }
//
//    @Override
//    public void forEach(BiConsumer<? super K, ? super V> action) {
//
//    }
//
//    @Override
//    public boolean remove(Object key, Object value) {
//        return false;
//    }
//
//    @Override
//    public boolean replace(K key, V oldValue, V newValue) {
//        return false;
//    }
//
//    @Override
//    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
//
//    }
//
//    @Override
//    public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
//        return null;
//    }
//
//    @Override
//    public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
//        return null;
//    }
//
//    @Override
//    public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
//        return null;
//    }
//
//    @Override
//    public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
//        return null;
//    }
//}
